using System.Runtime.InteropServices;

namespace Recast
{
	public unsafe partial class RecastGlobal
	{
		public unsafe partial class dtNodeQueue
		{
			public dtNode** m_heap;
			public int m_capacity;
			public int m_size;

			public dtNodeQueue() { }
			public dtNodeQueue(int n)
			{
				m_capacity = n;
				dtAssert(m_capacity > 0);
				m_heap = (dtNode**)dtAlloc(sizeof(dtNode*) * (m_capacity + 1), dtAllocHint.DT_ALLOC_PERM);
				//dtAssert(m_heap);
			}
			~dtNodeQueue()
			{
				dtFree(m_heap);
			}
			public void clear()
			{
				m_size = 0;
			}
			public dtNode* top()
			{
				return m_heap[0];
			}
			public dtNode* pop()
			{
				dtNode* result = m_heap[0];
				m_size--;
				trickleDown(0, m_heap[m_size]);
				return result;
			}
			public void push(dtNode* node)
			{
				m_size++;
				bubbleUp(m_size - 1, node);
			}
			public void modify(dtNode* node)
			{
				for (int i = 0; i < m_size; ++i)
				{
					if (m_heap[i] == node)
					{
						bubbleUp(i, node);
						return;
					}
				}
			}
			public bool empty()
			{
				return m_size == 0;
			}
			public int getMemUsed()
			{
				return Marshal.SizeOf(this) +
				sizeof(dtNode*) * (m_capacity + 1);
			}
			public int getCapacity()
			{
				return m_capacity;
			}
			//public int dtNodeQueue(ref dtNodeQueue @dtNodeQueue)
			//{
			//    return m_capacity;
			//}
			//            public dtNodeQueue& operator=(ref dtNodeQueue @dtNodeQueue) 
			//{ return m_capacity;}
			public void bubbleUp(int i, dtNode* node)
			{
				int parent = (i - 1) / 2;
				while ((i > 0) && (m_heap[parent]->total > node->total))
				{
					m_heap[i] = m_heap[parent];
					i = parent;
					parent = (i - 1) / 2;
				}
				m_heap[i] = node;
			}
			public void trickleDown(int i, dtNode* node)
			{
				int child = (i * 2) + 1;
				while (child < m_size)
				{
					if (((child + 1) < m_size) &&
					(m_heap[child]->total > m_heap[child + 1]->total))
					{
						child++;
					}
					m_heap[i] = m_heap[child];
					i = child;
					child = (i * 2) + 1;
				}
				bubbleUp(i, node);
			}
		}
	}
}
